package class28_KMP;

public class KMP {
    public static int kmp(String a, String b){
        int[] next = generateNext(b);
        char[] sc_a = a.toCharArray();
        char[] sc_b = b.toCharArray();
        int x=0;
        int y=0;

        while(true){
            if(y>=sc_b.length) return x - sc_b.length;
            if(x>=sc_a.length && y<sc_b.length) return -1;
            if(sc_a[x]==sc_b[y]){ x++; y++;}
            else{
                if(y==0) x++;
                else y=next[y];
            }
        }
    }

    public static int[] generateNext(String str){
        char[] sc = str.toCharArray();
        if(sc.length==0) return null;
        if(sc.length==1) return new int[]{-1};
        if(sc.length==2) return new int[]{-1,0};

        int[] next = new int[sc.length];
        next[0]=-1;
        next[1]=0;
        for(int i=2;i<sc.length;i++){
            int id = next[i-1];
            while(id!=-1 && sc[id]!=sc[i]) id = next[id];
            if(id==-1)next[i]=0;
            else next[i]=id+1;
        }
        return next;
    }

    public static void main(String[] args) {
        int ha = kmp("kjhabacbc","acb");
        int i=0;
    }
}
